package tree.structure.hashtree;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * @author: 26233
 * @create: 2022-08-02 10:13:29
 * @Description
 *
 * 哈希树（Merkle树，默克尔树）：根据质数分辨定理设计的可用于快速查找的数据结构
 *      a. 质数分辨定理：N个不同的质数可以 ”辨别“ 的连续整数的数量，与这些质数的乘积相同。
 *      b. 给定一串质数 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}，乘积 2 * 3 * ... * 29 = 6469696430
 *          而 Integer.MAX_VALUE = 2147483647
 * 哈希树构造：
 *      a. 对给定的数对质数串依次取余，如果余数的位置已存在，则换下一个质数,若余数不存在，则插入该位置。
 *      b. 2的余数位置: 0,1，
 *         3的余数位置有0,1,2
 *         5的余数位置有0,1,2,3,4
 *         ...
 *         余数的位置表示插入元素在该质数层节点的子节点插入位置
 *      c. 删除操作为逻辑删除，置删
 **/

public class HashTree {
    static private int[] PRIMES = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    private HashTreeNode root;
    public HashTree(){
        root = new HashTreeNode();
        root.setV(0);
        root.setEmpty(true);
        root.setLevel(0);
        // root.setNextNodes(new HashTreeNode[2]);
    }

    public void insert(HashTreeNode newNode){
        insert(newNode, root, 0);
    }
    public void insert(HashTreeNode newNode, HashTreeNode curNode, int level){
        int index = newNode.getV() % PRIMES[level];
        if (curNode.getNextNodes() == null) {
            curNode.setNextNodes(IntStream.range(0, PRIMES[curNode.getLevel()]).mapToObj(i -> {
                HashTreeNode hashTreeNode = new HashTreeNode();
                hashTreeNode.setLevel(level + 1);
                hashTreeNode.setEmpty(true);
                return hashTreeNode;
            }).toArray(HashTreeNode[]::new));
        }
        assert index < curNode.getNextNodes().length;
        if (curNode.getNextNodes()[index].isEmpty()) {
            curNode.getNextNodes()[index].setV(newNode.getV());
            curNode.getNextNodes()[index].setEmpty(false);
        }else {
            insert(newNode, curNode.getNextNodes()[index], curNode.getLevel());
        }
    }

    public static void main(String[] args) {

        int[] input = {78, 33, 18, 52, 74, 37, 29, 10, 94, 20, 56, 68};
        HashTree hashTree = new HashTree();
        Arrays.stream(input).forEach(e -> hashTree.insert(new HashTreeNode(e)));
        System.out.println("hashTree = " + hashTree);

    }
}
